package com.justnow.offer;

public class Solution63 {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = 0; //表示最大的价值的值
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }

    public int maxProfit2(int[] prices) {
        int mostLow = Integer.MAX_VALUE;
        int[] dp = new int[prices.length + 1];
        dp[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            mostLow = Math.min(mostLow, prices[i]);
            dp[i] = Math.max(dp[i-1], prices[i] - mostLow);
        }
        return dp[prices.length];
    }
}
